package demo;

import java.util.Deque;
import java.util.LinkedList;

/**
 *    重排链表
 *    L0 → L1 → … → Ln - 1 → Ln
 *    输出
 *    L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 */
class Solution32 {
	public void reorderList(ListNode head) {
		Deque<ListNode> deque = new LinkedList<>();
		ListNode curr = head.next;
		while (curr != null) {
			deque.offer(curr);
			curr = curr.next;
		}
		curr = head;
		int count = 0;
		while(!deque.isEmpty()) {
			if (count % 2 == 0) {
				curr.next = deque.pollLast();
			} else {
				curr.next = deque.poll();
			}
			curr = curr.next;
			count++;
		}
		curr.next = null;
	}
}

